import java.util.ArrayList;
import java.util.Arrays;

public class Solution {
    public static void main(String[] args) {
        Solution test = new Solution();
        System.out.println(test.triangleNumber(new int[]{4, 2, 3, 4}));
    }

    public int triangleNumber1(int[] nums) {
        /**
         * 有效三角形的个数
         * 暴力解法-稍作优化
         * 通过了，但是非常慢*/
        // 1 预处理
        int n = nums.length;
        Arrays.sort(nums);

        // 2 循环找
        int result = 0;
        for(int i = 0; i < n-2; i++) {
            for(int j = i+1; j < n-1; j++) {
                for(int k = j+1; k < n; k++) {
                    if(nums[i] + nums[j] > nums[k]) {
                        result ++;
                    }
                }
            }
        }

        // 3 返回值
        return result;
    }

    public int triangleNumber2(int[] nums) {
        /**
         * 有效三角形的个数
         * 优化：初步利用单调性，但还是有三重循环，不行*/
        // 1 预处理
        int n = nums.length;
        Arrays.sort(nums);

        // 2 循环找
        int result = 0;
        for(int i = 0; i < n-2; i++) {
            for(int j = i+1; j < n-1; j++) {
                int findIndex = n-1;
                while(findIndex > j && nums[i] + nums[j] <= nums[findIndex]) {
                    findIndex--;
                }
                result += findIndex - j;
            }
        }

        // 3 返回值
        return result;
    }

    public int triangleNumber(int[] nums) {
        /**
         * 有效三角形的个数
         * 优化：固定一个值，在剩余的待查找区间中利用升序的单调性，使用双指针算法进行快速判断*/
        // 1 预处理
        int n = nums.length;
        Arrays.sort(nums);

        // 2 循环找
        //- 2.1固定最大值
        int result = 0;
        for(int i = n-1; i >= 2; i--) {
            //- 2.2 在待查找区间使用双指针，引用区间最大值和最小值，由于区间有序，因此可以使用单调性
            int left = 0;
            int right = i-1;
            while(left < right) {
                if(nums[left] + nums[right] > nums[i]) {
                    //- 最小 + 区间最大都成立，那么任意 + 区间最大也成立
                    result += right - left;
                    right --;
                } else {
                    //- 最小 + 区间最大都不成立，那么最小 + 任意均不成立，舍去
                    left ++;
                }
            }
        }

        // 3 返回值
        return result;
    }
}
